package main

import "fmt"

//#link:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
func main() {
	s := "cbaebabacd"
	p := "abc"
	fmt.Println(findAnagrams(s, p))
}

//给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
//字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
func findAnagrams(s string, p string) []int {
	need, window := make(map[byte]int), make(map[byte]int)
	for _, letter := range []byte(p) {
		need[letter]++
	}
	validLen := 0
	left, right := 0, 0
	sByte := []byte(s)
	result := make([]int, 0)
	for right < len(s) {
		rLetter := sByte[right]
		right++
		//往窗口里面添加数据
		if value, ok := need[rLetter]; ok {
			window[rLetter]++
			if window[rLetter] == value {
				validLen++
			}
		}
		//判断是否需要缩小窗口空间
		for right-left >= len(p) {
			//当窗口符合条件时
			if validLen == len(need) {
				result = append(result, left)
			}
			lLetter := sByte[left]
			left++
			if value, ok := need[lLetter]; ok {
				if window[lLetter] == value {
					validLen--
				}
				window[lLetter]--
			}
		}
	}
	return result
}
